

// leetcode 57. 插入区间
//class Solution {
//    public int[][] insert(int[][] intervals, int[] newInterval) {
//        List<int[]> arr = new ArrayList<>();
//        // 需要将原数组中的 区间，跟新数组区间 有重合 的区间合并
//        // 没重合的区间直接添加
//        boolean flg = false;// 标记是否将重合区间合并完
//        // 记录合并后的重合区间
//        int left = newInterval[0], right = newInterval[1];
//        for (int i = 0; i < intervals.length; i++) {
//            // 重合区间在当前区间的左边
//            if (intervals[i][0] > right) {
//                if (!flg) {
//                    // 如果是第一次合并完重合区间，则需要添加进数组中
//                    arr.add(new int[]{left, right});
//                    flg = true;
//                }
//                arr.add(new int[]{intervals[i][0], intervals[i][1]});
//            } else if (intervals[i][1] < left) {
//                // 重合区间在当前区间的右边
//                arr.add(new int[]{intervals[i][0], intervals[i][1]});
//            } else {
//                // 区间重合了，则需要合并，并集
//                left = Math.min(intervals[i][0], left);
//                right = Math.max(intervals[i][1], right);
//            }
//        }
//
//        // 判断, 如果重合的区间是原数组最后一个区间
//        if (!flg) {
//            arr.add(new int[]{left, right});
//        }
//        return arr.toArray(new int[arr.size()][]);
//    }
//}